package tree.递归;

import po.TreeNode;

import java.util.*;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 二叉树的中序遍历94.java
 * @Description TODO  https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
 * @createTime 2021年03月06日 17:45:00
 */
public class 二叉树的中序遍历94 {

    /**
     * 递归的方式
     */
    List<Integer> treeNodeList = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return treeNodeList;
        }
        inorderTraversal(root.left);
        treeNodeList.add(root.val);
        inorderTraversal(root.right);
        return treeNodeList;
    }

    /**
     * 迭代 辅助栈
     */
    List<Integer> treeNodeList2 = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();

    public List<Integer> inorderTraversal2(TreeNode root) {
        if (root == null) {
            return treeNodeList2;
        }
        //外层循环遍历
        while (root != null || !stack.isEmpty()) {
            //内层循环构造栈结构
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode pop = stack.pop();
            treeNodeList2.add(pop.val);
            root = pop.right;
        }
        return treeNodeList2;
    }
}
